由於買了新遊戲所以昨天沒更新的我

1176. Diet Plan Performance (easy)
      https://leetcode.com/problems/diet-plan-performance/
      Submission：https://leetcode.com/problems/diet-plan-performance/submissions/854687100/

A dieter consumes calories[i] calories on the i-th day.

Given an integer k, for every consecutive sequence of k days (calories[i], calories[i+1], ..., calories[i+k-1] for all 0 <= i <= n-k), they look at T, the total calories consumed during that sequence of k days (calories[i] + calories[i+1] + ... + calories[i+k-1]):

If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.
Initially, the dieter has zero points. Return the total number of points the dieter has after dieting for calories.length days.

Note that the total points can be negative.
這題的敘述有夠長，讓我看了許久。
簡單來說就是要檢查每天卡路里的攝取量，若超過upper則加一分，若低於lower則扣一分，其他無視。

class Solution:
    def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
        def check(num):
            if num>upper:
                return 1
            elif num<lower:
                return -1
            else:
                return 0
        temp = sum(calories[:k])
        ans = check(temp)
        for i in range(k,len(calories)):
            temp -= calories[i-k]
            temp += calories[i]
            ans += check(temp)
        return ans

1196. How Many Apples Can You Put into the Basket (easy)
      https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket/
      Submission：https://leetcode.com/problems/how-many-apples-can-you-put-into-the-basket/submissions/854684601/
      You have some apples and a basket that can carry up to 5000 units of weight.

Given an integer array weight where weight[i] is the weight of the ith apple, return the maximum number of apples you can put in the basket.
簡單來說，你有個可以裝5000的菜籃，求最多可以裝多少東西(不可以超過限重)

所以就排列好，把所有小東西裝起來就對了

class Solution:
    #最大可以裝的重量為5000
    def maxNumberOfApples(self, weight: List[int]) -> int:
        weight.sort()
        ans = 0
        rec = 0
        for i in range(len(weight)):
            rec += weight[i]
            ans += 1
            if rec > 5000:
                return ans-1
        return len(weight)

784. Letter Case Permutation (medium)
     https://leetcode.com/problems/letter-case-permutation/
     Submission：https://leetcode.com/problems/letter-case-permutation/submissions/855772203/
     Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any order.
要列出該字串，把單獨或多個字母進行大小寫轉換，最終排列出所有組合

這題應該是要練習backtracking的演算法，但我對這演算法真的不熟，所以一開始用binary number的寫法解，接下來就參考別人backtracking寫法

class Solution:
    #把字母大小寫的每一種狀況都進行輸出
    
    #binary number
    def letterCasePermutation(self, s: str) -> List[str]:
        s = list(s.lower())
        letterS = [i for i in range(len(s)) if not s[i].isdigit()]
        lls = len(letterS)
        ans = []
        for i in range(2**lls):
            temp = bin(i)[2:].zfill(lls)
            tempL = s.copy()
            for i in range(len(temp)):
                if temp[i] == "1":
                    tempL[letterS[i]] = tempL[letterS[i]].upper() 
            ans.append("".join(tempL))
        return ans

    #參考別人寫法
class Solution(object):
    def letterCasePermutation(self, S):
        def backtrack(sub="", i=0):
            if len(sub) == len(S):#當長度等同於字串長度時
                res.append(sub)
            else:
                if S[i].isalpha():#判斷是不是字母
                #string.swapcase()可以把字母大寫變小寫，小寫變大寫
                    backtrack(sub + S[i].swapcase(), i + 1)
                backtrack(sub + S[i], i + 1)#不是字母就加數字&&加原字母
        res = []
        backtrack()
        return res

46. Permutations (medium)
    https://leetcode.com/problems/permutations
    Submission：https://leetcode.com/problems/permutations/submissions/854671898/
    Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order
    排列出所有數字組合

class Solution:
    #排列
    #把nums裡的數字重新排列，所有的排序都要排出來
    #任意順序
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        nL = len(nums)
        def backtracking(numList):
            if len(path) == nL:
                ans.append(path[:])
                return
            for i in range(0,len(numList)):
                # if numList[i] in path:
                #     continue
                path.append(numList[i])
                backtracking(numList[:i] + numList[i+1:]) #這樣就不用deepcopy
                path.pop()
        backtracking(nums)
        return ans

#別人的寫法
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtracking(nums, [], res)
        return res
        
    def backtracking(self, nums, curr, res):
        if not nums:
            res.append(curr)            
            return

        for i in range(len(nums)):
            #nums[i]是被抓走的值
            self.backtracking(nums[:i] + nums[i + 1:], curr + [nums[i]], res)

#別人的寫法
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def perm(items):
            if not items:
                return [[]]
            first_item = items[0]
            remain_items = items[1:]
            permu_remains = perm(remain_items)
            result = []
            for permu in permu_remains:
                for i in range(len(permu)+1):
                    result.append([*permu[:i], first_item, *permu[i:]])
            return result
        return perm(nums)

以上就是今天的練習感謝大家